package interval

import "math/bits"

const B = 64 // Block size for RMQ

type Comparator interface {
	Less(a, b int) bool
}

type LessComparator struct{}

func (c LessComparator) Less(a, b int) bool {
	return a < b
}

type GreaterComparator struct{}

func (c GreaterComparator) Less(a, b int) bool {
	return a > b
}

type RMQ struct {
	n   int
	cmp Comparator
	a   [][]int
	pre []int
	suf []int
	ini []int
	stk []uint64
}

func NewRMQ(v []int, cmp Comparator) *RMQ {
	rmq := &RMQ{cmp: cmp}
	rmq.init(v)
	return rmq
}

func min(a, b int, cmp Comparator) int {
	if cmp.Less(a, b) {
		return a
	}
	return b
}

func min3(a, b, c int, cmp Comparator) int {
	return min(min(a, b, cmp), c, cmp)
}

func lg(x int) int {
	return bits.Len(uint(x)) - 1
}

func ctz(x uint64) int {
	return bits.TrailingZeros64(x)
}

func (rmq *RMQ) init(v []int) {
	rmq.n = len(v)
	if rmq.n == 0 {
		return
	}

	rmq.pre = make([]int, rmq.n)
	rmq.suf = make([]int, rmq.n)
	rmq.ini = make([]int, rmq.n)
	copy(rmq.pre, v)
	copy(rmq.suf, v)
	copy(rmq.ini, v)

	rmq.stk = make([]uint64, rmq.n)

	M := (rmq.n-1)/B + 1
	lgM := lg(M)

	// Initialize sparse table
	rmq.a = make([][]int, lgM+1)
	for i := range rmq.a {
		rmq.a[i] = make([]int, M)
	}

	// Build first level
	for i := 0; i < M; i++ {
		rmq.a[0][i] = v[i*B]
		for j := 1; j < B && i*B+j < rmq.n; j++ {
			if rmq.cmp.Less(v[i*B+j], rmq.a[0][i]) {
				rmq.a[0][i] = v[i*B+j]
			}
		}
	}

	// Build prefix minimums
	for i := 1; i < rmq.n; i++ {
		if i%B != 0 {
			rmq.pre[i] = min(rmq.pre[i], rmq.pre[i-1], rmq.cmp)
		}
	}

	// Build suffix minimums
	for i := rmq.n - 2; i >= 0; i-- {
		if i%B != B-1 {
			rmq.suf[i] = min(rmq.suf[i], rmq.suf[i+1], rmq.cmp)
		}
	}

	// Build sparse table
	for j := 0; j < lgM; j++ {
		for i := 0; i+(2<<j) <= M; i++ {
			rmq.a[j+1][i] = min(rmq.a[j][i], rmq.a[j][i+(1<<j)], rmq.cmp)
		}
	}

	// Build stack values
	for i := 0; i < M; i++ {
		l := i * B
		r := min(rmq.n, l+B, rmq.cmp)
		var s uint64
		for j := l; j < r; j++ {
			for s > 0 && rmq.cmp.Less(v[j], v[lg(int(s))+l]) {
				s ^= 1 << lg(int(s))
			}
			s |= 1 << (j - l)
			rmq.stk[j] = s
		}
	}
}

func (rmq *RMQ) Query(l, r int) int {
	if l/B != (r-1)/B {
		ans := min(rmq.suf[l], rmq.pre[r-1], rmq.cmp)
		l = l/B + 1
		r = r / B
		if l < r {
			k := lg(r - l)
			ans = min3(ans, rmq.a[k][l], rmq.a[k][r-(1<<k)], rmq.cmp)
		}
		return ans
	} else {
		x := B * (l / B)
		return rmq.ini[ctz(rmq.stk[r-1]>>(l-x))+l]
	}
}
